/**
 * 给定一个数组A，再给定一个Target
 * 假设A的长度为N，则保证所有的Ai都在[1,N]之间 
 * N为4000
 * 
 * 反复问N个问题
 * for cap in [1, N]:
 *     所有数组元素均取min(Ai, cap)
 *     即所有大于cap的元素全取值为cap
 *     此情况下问能否选取若干个元素使得其值恰好为Target
 * 
 * 选若干个元素使得和恰好为目标，这是背包DP
 * 首先令cnt[i]记录i的数量，i属于[1,N]
 * 对i和cnt[i]做一个多重背包，注意多重背包要反着更新
 * 对N，直接取结果即可
 * for cap in [N-1,1]:
 *     首先计算出cap的数量cnt
 *     然后在D[cap-1]的基础上对cap做一个多重背包即可
 */
class Solution {

using vi = vector<int>;
vector<vi> D;
int N;
int Limit;

public:
    vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int k) {
        array<int, 4001> cnt{0};
        for(auto i : nums) cnt[i] += 1;
        Limit = k;
        N = nums.size();
        D.assign(N + 1, vi(Limit + 1, 0));
        D[0][0] = 1;

        // 做一个多重包
        for(int i=1;i<=N;++i){
            auto c = cnt[i];
            copy(D[i - 1].begin(), D[i - 1].end(), D[i].begin());
            for(int k=1;k<=c;k<<=1){
                int newV = k * i;
                for(int v=Limit;v>=newV;--v){
                    D[i][v] |= D[i][v - newV];
                }
                c -= k;
            }
            if(c > 0){
                int newV = c * i;
                for(int v=Limit;v>=newV;--v){
                    D[i][v] |= D[i][v - newV];
                }                
            }
        }

        vector<bool> ans(N, false);
        // N直接取答案即可
        ans[N - 1] = D[N][Limit];

        // 反向迭代
        int curCnt = cnt[N];
        for(int x=N-1;x>=1;--x){
            curCnt += cnt[x];
            copy(D[x - 1].begin(), D[x - 1].end(), D[x].begin());
            int tmpcnt = curCnt;
            // 开始往后更新，只有一步，就是一个多重背包
            for(int k=1;k<=tmpcnt;k<<=1){
                int newV = k * x;
                for(int v=Limit;v>=newV;--v){
                    D[x][v] |= D[x][v - newV];
                }
                tmpcnt -= k;
            }
            if(tmpcnt > 0){
                auto newV = tmpcnt * x;
                for(int v=Limit;v>=newV;--v){
                    D[x][v] |= D[x][v - newV];
                }
            }
            ans[x - 1] = D[x][Limit];
        } 
        return ans;    
    }
};